/**
 * 
 */
package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;

/**
 * @author zhong
 *
 */
public class MaximumFrequencyStack {

	class FreqStack {
		int i = 0;
		HashMap<Integer, Integer> frq;
		TreeMap<Integer, Set<Integer>> frq2N;
		HashMap<Integer, List<Integer>> N2Pos;

		public FreqStack() {
			frq = new HashMap<>();
			N2Pos = new HashMap<>();
			frq2N = new TreeMap<>();
		}

		public void push(int x) {
			i++;
			// freq
			int exCnt = frq.getOrDefault(x, 0);
			int cnt = exCnt + 1;
			frq.put(x, cnt);// 记录该值的当前次数

			// N2pos
			if (N2Pos.containsKey(x)) {// 保存位置信息
				N2Pos.get(x).add(i);
			} else {
				List<Integer> poses = new ArrayList<>();
				poses.add(i);
				N2Pos.put(x, poses);
			}
			// 更新freq到N的倒排
			if (exCnt != 0) {// 如果之前有这个元素，则先从对应freq里面删除它
				frq2N.get(exCnt).remove(x);
				if (frq2N.get(exCnt).isEmpty()) {// 删除完了之后如果是空，则删除对应<K,v>
					frq2N.remove(exCnt);
				}
			}
			if (frq2N.containsKey(cnt)) {// 新：
				frq2N.get(cnt).add(x);
			} else {
				Set<Integer> set = new HashSet<>();
				set.add(x);
				frq2N.put(cnt, set);
			}
		}

		public int pop() {
			int maxCnt = frq2N.lastKey();// 最大次数
			// 找到这些N中的最大位置对应的N，移除最大位置
			int maxPos = 0;
			Set<Integer> set = frq2N.get(maxCnt);
			int x = 0;
			for (Integer integer : set) {// 最大次数的每个元素
				int mostRecent = N2Pos.get(integer).get(N2Pos.get(integer).size() - 1);// 该元素最近加入的位置
				if (maxPos < mostRecent) {
					maxPos = mostRecent;
					x = integer;
				}
			}

			// 更新
			int exCnt = maxCnt;
			int cnt = exCnt - 1;
			if (cnt != 0) {
				frq.put(x, cnt);// 记录该值的当前次数
			} else {
				frq.remove(x);
			}
			// 更新freq2N
			frq2N.get(maxCnt).remove(x);// 旧
			if (frq2N.get(maxCnt).isEmpty()) {
				frq2N.remove(maxCnt);
			}
			if (frq2N.containsKey(cnt)) {// 新
				frq2N.get(cnt).add(x);
			} else {
				Set<Integer> set2 = new HashSet<>();
				set.add(x);
				frq2N.put(cnt, set2);
			}

			// N2pos
			N2Pos.get(x).remove(N2Pos.get(x).size() - 1);// 旧，移除刚刚位置对应的1个元素

			return x;
		}
	}

	public void test() {
		FreqStack f = new FreqStack();
		f.push(5);
		f.push(7);
		f.push(5);
		f.push(7);
		f.push(4);
		f.push(5);
		System.out.println(f.pop());
		System.out.println(f.pop());
		System.out.println(f.pop());
		System.out.println(f.pop());
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new MaximumFrequencyStack().test();
	}

}
